package cn.fxzhang.leetcode.no02;

/**
 * 213. 打家劫舍 II
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * 输入：nums = [2,3,2]
 * 输出：3
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 1000
 *
 * 类型：动态规划
 * 题解：
 * f[i]表示第1个不取时，取第i个时的最大金额，f[i]=max(f[k])+nums[i],1<=k<i-2,1<=i<=n-1
 * g[i]表示第1个取时，，取第i个时的最大金额，g[i]=max(g[k])+nums[i],0<=k<i-2,i<n-1
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 5 ms, 击败了100.00%
 * 内存消耗: 35.9 MB, 击败了31.00%
 *
 * 【中等】通过次数89,775提交次数215,668
 * @date 2021/4/15
 */
public class P0213_House_Robber_Ii {

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1){
            return nums[0];
        }
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = 0;
        g[0] = nums[0];
        f[1] = nums[1];
        g[1] = 0;
        int max = Math.max(nums[0], nums[1]);

        for (int i=2; i<n; i++){
            for (int k=0; k<=i-2; k++){
                f[i] = Math.max(f[k]+nums[i], f[i]);
                g[i] = Math.max(g[k]+nums[i], g[i]);
            }
            max = Math.max(max, f[i]);
            // 第1个取了，所以最后1个不能取
            if (i<n-1){
                max = Math.max(max, g[i]);
            }
        }
        return max;
    }
}
